package huawei.test;

import java.util.*;

/**
 * 问题描述
 * 在一棵树中，每个节点代表一个家庭成员，节点的数字表示其个人的财富值，一个节点及其直接相连的子节点被定义为一个小家庭。
 *
 * 现给你一棵树，请计算出最富裕的小家庭的财富和。
 *
 * 输入格式
 * 第一行包含一个整数
 * 𝑁
 * N，表示成员总数，成员编号为
 * 1
 * 1 到
 * 𝑁
 * N，
 * 1
 * ≤
 * 𝑁
 * ≤
 * 100
 * 1≤N≤100。
 *
 * 第二行包含
 * 𝑁
 * N 个空格分隔的整数，表示编号
 * 1
 * 1 到
 * 𝑁
 * N 的成员的财富值，
 * 0
 * ≤
 * 财
 * 富
 * 值
 * ≤
 * 1000000
 * 0≤财富值≤1000000。
 *
 * 接下来
 * 𝑁
 * −
 * 1
 * N−1 行，每行包含两个空格分隔的整数
 * 𝑁
 * 1
 * N1 和
 * 𝑁
 * 2
 * N2，表示
 * 𝑁
 * 1
 * N1 是
 * 𝑁
 * 2
 * N2 的父节点。
 *
 * 输出格式
 * 输出最富裕的小家庭的财富和。
 *
 * 样例输入
 * 样例 1
 *
 * 4
 * 100 200 300 500
 * 1 2
 * 1 3
 * 2 4
 *
 * 作者：清隆学长a
 * 链接：https://www.nowcoder.com/discuss/636507146279993344
 * 来源：牛客网
 */
public class MostReachFamily {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 节点总数
        int num = Integer.parseInt(sc.nextLine());
        int[] weights = Arrays.stream(sc.nextLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        // 父子关系
        Map<Integer, List<Integer>> tree = new LinkedHashMap<>(num);
        for (int i = 0; i < num - 1; i++) {
            int parent = sc.nextInt();
            int child = sc.nextInt();
            tree.computeIfAbsent(parent, ArrayList::new).add(child);
        }

        int maxVal = 0;
        for (int i = 1; i <= num; i++) {
            if (tree.containsKey(i)) {
                int parentVal = weights[i - 1];
                Integer childVal = tree.get(i).stream()
                        .map(index -> weights[index - 1])
                        .reduce(Integer::sum)
                        .get();
                maxVal = Math.max(maxVal, (parentVal + childVal));
            }
        }
        System.out.println("最富有的家庭的家庭财富值是"+maxVal);
    }
}
